package clases;


public class Dijkstra
{
	// Algoritmo de Dijkstra
	public static double dijkstra(Digrafo digrafo, int origen, int destino)
	{
		// Distancias tentativas y nodos visitados
		int n = digrafo.getCantidadDeNodos();
		int actual = origen;
		boolean[] visitado = new boolean[n];
		double[] d = inicializarDistancias(origen, n);
		
		// Iteraciones
		while( actual != destino )
		{
			propagarDistancias(digrafo, actual, d);
			marcarComoVisitado(actual, visitado);
			actual = menorNoVisitado(visitado, d);
		}
		
		return d[destino];
	}

	// Marca un nodo como visitado
	private static void marcarComoVisitado(int i, boolean[] visitado)
	{
		visitado[i] = true;
	}

	// Actualiza las distancias tentativas de los vecinos del nodo actual
	private static void propagarDistancias(Digrafo digrafo, int actual, double[] d)
	{
		for(Digrafo.Arco arco: digrafo.getVecinos(actual))
		{
			double dprima = d[actual] + arco.distancia;
			if( dprima < d[arco.nodo] )
				d[arco.nodo] = dprima;
		}
	}

	// Inicializa las distancias tentativas, en cero para el origen
	// y en infinito para el resto
	private static double[] inicializarDistancias(int origen, int n)
	{
		double[] d = new double[n];
		for(int i=0; i<n; ++i)
			d[i] = i == origen ? 0 : Double.MAX_VALUE;
		
		return d;
	}
	
	// Busca el nodo no visitado con menor distancia tentativa
	private static int menorNoVisitado(boolean[] visitado, double[] d)
	{
		double menorD = Double.MAX_VALUE;
		int ret = 0;
		
		for(int i=0; i<visitado.length; ++i)
		{
			if( visitado[i] == false && d[i] <= menorD )
			{
				menorD = d[i];
				ret = i;
			}				
		}
		
		return ret;
	}
}
